
/**
 * O(n ^ 2), S(n * log(n))
 */
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 身高h_i从高到底, 序号k_i从小到大
        Arrays.sort(people, (int[] arr1, int[] arr2) -> { // S(n * log(n))
            return -(arr1[0] - arr2[0]) == 0? arr1[1] - arr2[1]: -(arr1[0] - arr2[0]);
        });

        List<int[]> list = new LinkedList<>();

        for(int[] arr: people){ // 插入后移 O(n ^ 2)
            list.add(arr[1], arr); // 排序后, 第一个人时, 身高最高, 且序号一定为0. 后面人加入时, 前面已加入的人的身高都大于等于目前这个人了, 则只需要按序号从中间插入即可, 并不会影响之前的人的序号, 因为之前的人的身高都大于这个人.
        }

        return list.toArray(new int[][]{});
    }
}